package main

import (
	"fmt"
	"go-study/algorithm/standard"
)

// 如何找出排序二叉树上任意两个节点的最近共同父节点

func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	root := standard.ArrayToTree(data, 0, len(data)-1)
	node1 := root.LeftChild.LeftChild.LeftChild
	node2 := root.LeftChild.RightChild
	fmt.Println(findParentNode(root, node1, node2).Data)
	fmt.Println(findParentNodeNum(root, node1, node2).Data)
	fmt.Println(findParentNodeReverse(root, node1, node2).Data)
}

// 方法一：
// 路径对比法
func findParentNode(root, node1, node2 *standard.BNode) *standard.BNode {
	stack1 := standard.NewSliceStack()
	stack2 := standard.NewSliceStack()

	getPathFromRoot(root, node1, stack1)
	getPathFromRoot(root, node2, stack2)

	var commonParent *standard.BNode
	t1 := stack1.Pop().(*standard.BNode)
	t2 := stack2.Pop().(*standard.BNode)

	for t1 != nil && t2 != nil && t1 == t2 {
		commonParent = t1
		t1 = stack1.Pop().(*standard.BNode)
		t2 = stack2.Pop().(*standard.BNode)
	}

	return commonParent
}

// 获取二叉树从根节点 root 到 node 节点的路径
func getPathFromRoot(root *standard.BNode, node *standard.BNode, s *standard.SliceStack) bool {
	if root == nil {
		return false
	}

	if root == node {
		s.Push(root)
		return true
	}

	if getPathFromRoot(root.LeftChild, node, s) || getPathFromRoot(root.RightChild, node, s) {
		s.Push(root)
		return true
	}

	return false
}

// 方法二：
// 节点编号法
func findParentNodeNum(root, node1, node2 *standard.BNode) *standard.BNode {
	_, num1 := getNumber(root, node1, 1)
	_, num2 := getNumber(root, node2, 1)
	for num1 != num2 {
		if num1 > num2 {
			num1 /= 2
		} else {
			num2 /= 2
		}
	}

	return getNodeFromNum(root, num1)
}

// 根据编号找到对应的节点
func getNodeFromNum(root *standard.BNode, number int) *standard.BNode {
	if root == nil || number <= 0 {
		return nil
	}

	if number == 1 {
		return root
	}

	for number != 1 {
		if number%2 == 0 {
			root = root.LeftChild
		} else {
			root = root.RightChild
		}
		number /= 2
	}

	return root
}

// 找出节点在二叉树中的编号
func getNumber(root, node *standard.BNode, number int) (bool, int) {
	if root == nil {
		return false, number
	}
	if root == node {
		return true, number
	}
	if b, num := getNumber(root.LeftChild, node, number*2); b {
		return true, num
	}

	return getNumber(root.RightChild, node, number*2+1)
}

// 方法三：后续遍历法
func findParentNodeReverse(root, node1, node2 *standard.BNode) *standard.BNode {
	if root == nil || root == node1 || root == node2 {
		return root
	}
	leftChild := findParentNodeReverse(root.LeftChild, node1, node2)
	rightChild := findParentNodeReverse(root.RightChild, node1, node2)

	if leftChild == nil {
		return rightChild
	}

	if rightChild == nil {
		return leftChild
	}

	return root
}
